Майнор "Интеллектуальный анализ данных" ¶
Курс "Введение в анализ данных" ¶
Лабораторная работа №2. Кластерный анализ. ¶
Часть 1¶
В данном задании вам необходимо самостоятельно реализовать один из алгоритмов кластеризации.
По аналогии с классами в scikit-learn, нужно реализовать класс, наследуемый от Base Estimator.
Подробнее про реализацию своих моделей в scikit-learn: here.
В классе помимо __init__() нужно реализовать два метода:
fit()- метод, выполняющий кластеризацию данных.predict()- метод, определяющий для нового объекта, к какому из кластеров он относится.
Для удобства можно создавать дополнительные методы класса, которые будут вызываться в fit() или predict().
Функции для вычисления расстояний между объектами самим реализовывать не нужно, используйте реализации из scipy.
# Не до конца получилось реализовать на момент отправления работы
import numpy as np
from scipy.spatial import distance
from sklearn.base import BaseEstimator, ClusterMixin
class My_Clust(BaseEstimator, ClusterMixin):
"""
My implementation of clustering algorithm
"""
def __init__(self, n_clusters=8, init='k-means++', n_init=10, max_iter=500, tol=0.0001):
self.inertia_ = 0
self.cluster_centers_ = list()
self.labels_ = list()
self.X_ = None
self.y_ = None
self.size_ = 0
self.n_clusters = n_clusters
self.init = init
self.n_init = n_init
self.max_iter = max_iter
self.tol = tol
def get_labels(self):
return self.labels_
def get_params(self, deep=True):
return {
"n_clusters": self.n_clusters,
"init": self.init,
"n_init": self.n_init,
"max_iter": self.max_iter,
"tol": self.tol,
}
def set_params(self, **params):
for parameter, value in params.items():
setattr(self, parameter, value)
return self
def fit(self, X, y=None):
self.X_ = np.array(X)
self.size_ = len(self.X_)
solutions_list = list()
n, p = X.shape
for i in range(self.n_init):
self.cluster_centers_ = list()
self.labels_ = [0 for i in range(self.size_)]
centers = np.random.choice(n, size=self.n_clusters, replace=False)
centers = X[centers, :]
center_buf = centers
center_buf_2 = centers
clusters_result = []
distances = np.zeros((n, self.n_clusters))
for loop in range(self.max_iter):
center_buf_2 = center_buf
for i in range(n):
for j in range(self.n_clusters):
distances[i, j] = distance.euclidean(X[i], center_buf[j])
clusters_result = np.argmin(distances, 1)
for i in range(self.n_clusters):
check = False
for j in range(n):
if (clusters_result[j] == i):
check = True
if (check):
center_buf[i] = np.mean(X[clusters_result == i], 0)
self.labels_ = clusters_result
return self
my_kmeans = My_Clust(n_clusters=3, init='k-means++')
my_kmeans.fit(iris.data)
Вариант №3¶
Алгоритм K-Means.
Параметры:
- k: число центров (кластеров);
- init: метод инициализации центров - random или kmeans++;
- n_init: число запусков алгоритма;
- max_iter: максимальное число итераций;
- tol: минимальное значение изменения целевой функции.
Атрибуты:
- inertia_: Итоговое значение целевой функции;
- cluster_centers_: центры кластеров - ndarray of shape (n_clusters, n_features);
- labels_: метки кластеров для каждого объекта.
Метод predict(): Новый объект определяется в кластер, центр которого расположен ближе всех к этому объекту.
Тестирование¶
Вашу реализацию необходимо сравнить с питоновской реализацией алгоритма из sklearn или scipy. Результаты кластеризации должны совпадать.
Также необходимо сравнить скорость работы вашей реализации и питоновской (это нормально, если ваша реализация будет медленнее).
Сравнение необходимо выполнить на наборе данных iris.
import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
import seaborn as sns
iris = load_iris()
X = iris.data # использовать для кластеризации
y = iris.target # истинные метки цветков
X = pd.DataFrame(X, columns=iris.feature_names)
X['class'] = [iris.target_names[i] for i in y]
sns.pairplot(X, hue='class', plot_kws={'alpha':0.5}, vars=iris.feature_names)
plt.show()
Бонусное¶
Дополнительно вы можете поработать над эффективностью алгоритма по скорости и памяти, добавить поддержку многопоточности, или расширить базовый функционал.
import time
iris_p = iris.data.copy()
my_kmeans = My_Clust(n_clusters=3, init='k-means++')
start_time = time.clock()
my_kmeans.fit(iris_p)
my_time = time.clock() - start_time
labels = my_kmeans.get_labels()
iris_p['class'] = labels
sns.pairplot(iris_p, hue='class', plot_kws={'alpha': 0.75}, vars=iris.feature_names)
plt.show()
Часть 2¶
В данном задании вам предлагается проанализировать набор данных по различным городам США. Каждый город характеризуется следующими признаками:
pd.set_option('display.max_colwidth', None)
data_desc = pd.read_csv('Data_Description.txt', sep=':')
data_desc
Notes:¶
- Для всех признаков, кроме трех, чем выше значение - тем лучше. Для признаков
HousingиCrime- наоборот. - Признак
Population- статистический признак, не имеющий интерпретации как “лучше-хуже”. - Признак
Place- уникальный идентификатор объекта (города), он не должен использоваться при кластеризации. - Также в данных присутствуют географические координаты городов -
LongitudeиLatitude. Их также не следует использовать при кластеризации данных.
Задания:¶
- Выполните необходимую предобработку данных. Перед кластеризацией исключите из данных признаки Place, Long и Lat.
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import scipy.cluster.hierarchy as h
data = pd.read_csv('Data.txt', sep=' ')
data
# Стандартизация данных
from sklearn.preprocessing import MinMaxScaler
minmax = MinMaxScaler()
data_updated = data[['Climate', 'HousingCost', 'HlthCare', 'Crime', 'Transp' , 'Educ', 'Arts', 'Recreat', 'Econ', 'Pop']]
data_transformed = minmax.fit_transform(data_updated)
data_scaled = pd.DataFrame(data_transformed, columns=data_updated.columns)
data_scaled
- Выполните кластеризацию иерархическим методом. Рассмотрите различные расстояния между объектами. Определите, какие следует использовать при кластеризации. Выполните кластеризацию с различными расстояниями между кластерами. Сравните результаты, сделайте выводы.
for m in ['euclidean', 'minkowski', 'cityblock']:
Z = h.linkage(data_scaled, metric=m, method='complete')
plt.figure(figsize=(50, 25))
h.dendrogram(Z, p=50)
plt.show()
from sklearn.metrics import silhouette_score
for m in ['euclidean', 'minkowski', 'cityblock']:
Z = h.linkage(data_scaled, metric=m, method='complete')
labels_h = h.fcluster(Z, t=3, criterion='maxclust')
print('metric:' + m)
print(silhouette_score(data_scaled, labels_h), '\n')
for m in ['euclidean', 'minkowski', 'cityblock']:
Z = h.linkage(data_scaled, metric=m, method='complete')
labels_h = h.fcluster(Z, t=4, criterion='maxclust')
print('metric:' + m)
print(silhouette_score(data_scaled, labels_h), '\n')
for m in ['euclidean', 'minkowski', 'cityblock']:
Z = h.linkage(data_scaled, metric=m, method='complete')
labels_h = h.fcluster(Z, t=5, criterion='maxclust')
print('metric:' + m)
print(silhouette_score(data_scaled, labels_h), '\n')
Комментарий:¶
Сityblock выдал результат лучше при 3-4 кластерах, в то время как при 5 кластерах euclidean & minkowski были лучше. Сейчас и далее эффективность я буду оценивать метрикой silhouette_score
# Рассмотрим различные расстояниям между кластерами
for M in ['single', 'complete', 'average', 'weighted', 'centroid', 'median', 'ward']:
Z = h.linkage(data_scaled, metric='euclidean', method=M)
plt.figure(figsize=(15,10))
plt.title(M)
_=h.dendrogram(Z, p=50, truncate_mode='lastp')
for M in ['single', 'complete', 'average', 'weighted', 'centroid', 'median', 'ward']:
max_score = 0
clusters_num = 0
for N in range(3, 10):
Z = h.linkage(data_scaled, method=M)
labels_h = h.fcluster(Z, t=N, criterion='maxclust')
initial = silhouette_score(data_scaled, labels_h)
if initial > max_score:
max_score = initial
clusters_num = N
print('method:' + M + '\nclusters number:', clusters_num, '\nSilhouette score:', max_score, '\n')
for M in ['single', 'complete', 'average', 'weighted']:
max_score = 0
clusters_num = 0
for N in range(3, 10):
Z = h.linkage(data_scaled, metric='cityblock', method=M)
labels_h = h.fcluster(Z, t=N, criterion='maxclust')
initial = silhouette_score(data_scaled, labels_h)
if initial > max_score:
max_score = initial
clusters_num = N
print('method:' + M + '\nclusters number:', clusters_num, '\nSilhouette score:', max_score, '\n')
Комментарий:¶
Лучше всего себя показали методы single и median с количеством кластеров - 3 и метрикой euclidean. Такой же результат был у single с кол-вом кластеров - 3 и метрикой cityblock.
import warnings
warnings.filterwarnings('ignore')
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='single', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='median', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='single', metric='cityblock')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
Комментарий:¶
Несмотря на неплохой результат silhouette_score, результат вышел плохим. Существует один большой кластер, а остальные кластеры - отдельные точки. Поэтому необходимо перебрать другие вариант, которые, возможно, показали себя не так хорошо по результатам метрики.
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='complete', metric='cityblock')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='weighted', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='centroid', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
h_cluster = h.linkage(data_pred, method='ward', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
Комментарий:¶
Визуально method='ward' и metric='euclidean' выглядят гораздо лучше, видно не один большой кластер, а несколько. Проверим еще другое кол-во кластеров.
h_cluster = h.linkage(data_pred, method='ward', metric='euclidean')
labels = h.fcluster(h_cluster, t=4, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
h_cluster = h.linkage(data_pred, method='ward', metric='euclidean')
labels = h.fcluster(h_cluster, t=5, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
Комментарий:¶
По итогу я склоняюсь к 4 кластерам, мне кажется, это оптимальное кол-во.
- Выполните кластеризацию методом Dbscan. Используйте расстояния между объектами, определенные в предыдущем пункте. Реализуйте эвристику (см. лекции) для выбора параметров алгоритма. Подберите подходящие параметры алгоритма.
from sklearn.cluster import DBSCAN
for E in np.arange(0.5, 3, 0.5):
for MS in range(3, 7):
db_cluster = DBSCAN(eps=E, min_samples=MS, metric='euclidean').fit(data_pred)
labels = db_cluster.labels_
print(E, MS, '\n', pd.Series(labels).value_counts(), '\n')
Комментарий:¶
Наиболее подходящими кажутся значение 1.0 для eps и min_samples = 3.
db_cluster = DBSCAN(eps=1.0, min_samples=3, metric='euclidean').fit(data_pred)
labels = db_cluster.labels_
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
Комментарий:¶
Мне кажется, что 5 кластеров является оптимальным количеством.
- Выполните кластеризацию методом kmeans. Определите наилучшее (на ваш взгляд) число кластеров.
from sklearn.cluster import KMeans
plt.figure(figsize=(15, 10))
inertia = []
# Определяем оптимальное кол-во кластеров
for i in range(2, 20):
kmeans = KMeans(n_clusters=i, n_init=10)
kmeans.fit(data_scaled)
labels = kmeans.predict(data_scaled)
inertia.append(kmeans.inertia_)
plt.plot(range(2, 20), inertia, 'x-r')
plt.show()
Комментарий:¶
Мне показалось, что 7 кластеров подходят в данном случае лучше всего, но я решила еще раз удостовериться в последующих экспериментах.
kmeans = KMeans(n_clusters=7, n_init=10)
kmeans.fit(data_scaled)
labels_kmeans = kmeans.predict(data_scaled)
print(labels_kmeans)
[sum(labels_kmeans==x) for x in range(7)]
for N in range(4,8):
k_cluster = KMeans(n_clusters=N, init='k-means++', random_state=3).fit(data_pred)
labels = k_cluster.labels_
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
Комментарий:¶
Мне показалось, что наиболее подходящими выглядят 5 и 7 кластеров, но я все равно оставлю предпочтение последнему.
- (Бонусное) Выполните кластеризацию другими методами. Например, HDBSCAN или алгоритмы, реализованные в scikit-learn.
from hdbscan import HDBSCAN, hdbscan
hdb_cluster = hdbscan.HDBSCAN(min_cluster_size=14, gen_min_span_tree=True)
hdb_cluster.fit(data_pred)
labels = hdb_cluster.labels_
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
pd.Series(cl_hdbscan.labels_).value_counts()
pip install numpy --upgrade
- В результате выполнения предыдущих пунктов вы должны получить 4 или больше разбиений объектов (по одному на каждый метод). Сравните их между собой, сделайте выводы о сходствах и различиях. Оцените результаты каждой кластеризации, используя метрики, рассмотренные на занятиях (Silhouette и прочие).
# Silhouette_score
h_cluster = h.linkage(data_scaled, method='ward', metric='euclidean')
labels_h = h.fcluster(h_cluster, t=4, criterion='maxclust')
db_cluster = DBSCAN(eps=1.0, min_samples=3, metric='euclidean').fit(data_pred)
labels_db = db_cluster.labels_
k_cluster = KMeans(n_clusters=N, init='k-means++', random_state=3).fit(data_scaled)
labels_kmeans = k_cluster.labels_
silhouette_score(data_scaled, labels_h)
silhouette_score(data_scaled, labels_db)
silhouette_score(data_scaled, labels_kmeans)
from sklearn.metrics import calinski_harabasz_score
calinski_harabasz_score(data_scaled, labels_h)
calinski_harabasz_score(data_scaled, labels_db)
calinski_harabasz_score(data_scaled, labels_kmeans)
from sklearn.metrics import davies_bouldin_score
davies_bouldin_score(data_scaled, labels_h)
davies_bouldin_score(data_scaled, labels_db)
davies_bouldin_score(data_scaled, labels_kmeans)
- Выберите одно разбиение, наиболее подходящее на ваш взгляд. Предложите интерпретацию полученным кластерам или покажите, что этого сделать нельзя.
Комментарий:¶
Как мне показалось, наиболее подходящим разбиением вышло K-means
data_pred['class'] = labels_kmeans
data = [data.loc[data_pred['class'] == i] for i in range(7)]
data[0]
data[1]
data[2]
data[3]
data[4]
data[5]
data[6]
Комментарий:¶
Показатель Educ не сильно отличается от класса к классу.
Класс 0:¶
Средний HousingCost, большая Population, хорошо развит Transp
Класс 1:¶
HousingCost ниже среднего, высокий Econ, низкий Arts, низкая Pop.
Класс 2:¶
HousingCost ниже среднего, средний показатель HlthCare, низкий Crime, экономический показатель невысокий, низкий Arts, низкая Pop.
Класс 3:¶
HousingCost самый дорогой, большая Population, низкий Crime, высокий Econ. Группа городов, которая очень хороша для проживания, несмотря на высокую цену жилья. Географически самые теплые страны.
Класс 4:¶
HousingCost ниже среднего, экономический показатель невысокий
Класс 5:¶
Cредний HousingCost, низкая Pop.
Класс 6:¶
Высокая HousingCost, высокий показатель HlthCare (выше, чем у остальных групп), впрочем, как и большинство показателей (Crime, Transp, Educ, Arts (очень сильно отличается от остальных)). Pop гораздо больше остальных, что говрит нам о том, что в данной группе наиболее большие города Америки.
- Оцените, как полученные кластеры распределены географически.
Оцените, как полученные кластеры распределены по штатам. Можно ли выделить какую-то зависимость (территориальную или для штатов)?
(Бонусное) Провизуализируйте распределение на карте США.
pip install folium
import folium
colors = {
0: "green",
1: "pink",
2: "blue",
3: "orange",
4: "purple",
5: 'lightgreen',
6: "red"
}
_map = folium.Map(location=[39.091431, -96.655998], zoom_start=4)
for i in range(len(data)):
for index, city in data[i].iterrows():
folium.Marker(
location=[city["Lat"], city["Long"]],
icon=folium.Icon(color=colors[i]),
).add_to(_map)
_map
Комментарий:¶
Действительно, зеленый кластер (0) - это достаточно крупные города (иногда даже столицы) в разных штатах (Вирджинии, Кентукки и других). Розовый (1), как и следовала ожидать, содержит города Америки, которые вряд ли кто-то знает (они небольшие). 2 кластер, голубой, сход с первым. Города третьего кластера (оранжевый) могут быть на слуху, они находятся преимущественно на побережьях, что делает цены на жилье высокими. Кластер 4, здесь можно встретить знакомые названия городов, но до сих пор это не самые развитые города. Как первый и второй кластеры преимущественно находится в центральной части Америки. Светло-зеленый кластер (5) географически находится на побережье страны, но не в таких дорогих местах, как 3 кластер. А последний кластер (6) - это крупные города и популярные города.